/*
 * @lc app=leetcode.cn id=123 lang=java
 *
 * [123] 买卖股票的最佳时机 III
 */

// @lc code=start
class Solution {
    //限制交易次数为2比了，那么如何找出利润最大的两笔交易呢？
    public int maxProfit(int[] prices) {
        //这是形式更简单，更容易推广的dp
        int[][] t = new int[2][2];//int[交易次数][0代表持股，1代表未持股]
        t[0][0] = Integer.MIN_VALUE;//初始未持股时设未最小值。
        t[1][0] = Integer.MIN_VALUE;//初始未持股时设未最小值。
        for(int p : prices) {
            t[0][0] = Math.max(t[0][0], -p);//未交易，持股
            t[0][1] = Math.max(t[0][1], t[0][0] + p);//未交易，且未持股
            for(int i = 1; i < 2; ++i) {//状态转移方程
                t[i][0] = Math.max(t[i][0], t[i-1][1] - p);//要么维持上次的持股状态，要么由未持股转持股，花钱
                t[i][1] = Math.max(t[i][1], t[i][0] + p);//要么维持上次的未持股状态，要么由持股转未持股，赚钱
            }
        }
        return t[1][1];//最后交易次数转
    }


    public int maxProfit2(int[] prices) {
        //动态规划
        // dp[天数][当前是否持股][卖出的次数]
        // dp里面存的相当于是剩余的钱，也可说是利润
        int len = prices.length;
        int[][][] dp = new int[len][2][3];
        //给定转移方程初始值
        dp[0][0][0] = 0;
        dp[0][0][1] = -99999;
        dp[0][0][2] = Integer.MIN_VALUE;//同样在一开始不可能
        dp[0][1][0] = -prices[0];//第0天持股，那么表明肯定是花钱买了第0天的股票
        dp[0][1][1] = Integer.MIN_VALUE;

        dp[0][1][2] = Integer.MIN_VALUE;//这个不可能

        for(int i=1;i<len;i++){//i要从1开始，不然i-1会越界。
            //注意顺序无所谓，因为都是在用上一层的值

            dp[i][0][0] = 0;
            // 前一天持股，今天卖出   前一天不持股，且卖出
            dp[i][0][1] = Math.max(dp[i-1][1][0]+prices[i],dp[i-1][0][1]);
            // 同上一条
            dp[i][0][2] = Math.max(dp[i-1][1][1]+prices[i],dp[i-1][0][2]);

            //购入股票，或者维持上一个状态
            dp[i][1][0] = Math.max(dp[i-1][0][0]-prices[i],dp[i-1][1][0]);

            //可能是昨天没买，今天才持股的，也是购入股票，用减法
            // 注意这里dp[0][0][1]不能是Integer.MIN_VALUE，因为这样减去一个数之后直接越界变成正值
            // 稍微小一点即可
            dp[i][1][1] = Math.max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]);

            //这个不用更新
            // dp[i][1][2] = Math.max(dp[i-1][0][2]+prices[i],dp[i-1][1][1]);
        }

        return Math.max(0 , Math.max(dp[len-1][0][2], dp[len-1][0][1]) );
        //当前不持股，且卖出两次的最大值即为结果，注意可能是递增数列，那么只会进行一次交易

    }
    public int maxProfit1(int[] prices) {
        /**
        对于任意一天考虑四个变量:
        fstBuy: 在该天第一次买入股票可获得的最大收益 
        fstSell: 在该天第一次卖出股票可获得的最大收益
        secBuy: 在该天第二次买入股票可获得的最大收益
        secSell: 在该天第二次卖出股票可获得的最大收益
        分别对四个变量进行相应的更新, 最后secSell就是最大
        收益值(secSell >= fstSell)
        **/
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int p : prices) {
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy + p); 
        }
        return secSell;
        // 把secBuy和secSell去掉，返回值改成fstSell就成了121题的解法
    }
    
}
// @lc code=end

